import turtle
# created by guxuan
class Maze:
    def __init__(self,mazeFilePath):
        rowsInMaze = 0  # 初始化行
        columnsInMaze = 0   # 初始化列
        self.mazelist = []  # 存储迷宫列表

        mazefile = open(mazeFilePath,'r')   # 按行打开文件
        for line in mazefile:   # 遍历，每个line是一行
            rowList = []    # 行列表，每一行一个列表存储
            col = 0
            for ch in line:    # 每行最后一个换行符要去掉
                rowList.append(ch)
                if ch == 'S':   # 保存海龟的初始位置
                    self.startRow = rowsInMaze
                    self.startCol = col
                col = col + 1
            rowsInMaze = rowsInMaze + 1
            self.mazelist.append(rowList)   # 列表中加入一行
            columnsInMaze = len(rowList)    # 列的数量

        # 上面整个地图读取完毕,初始化地图的行和列
        self.rowsInMaze = rowsInMaze
        self.columsInMaze = columnsInMaze

        # 初始化海归地图的坐标
        self.XTranslate = -columnsInMaze/2 + 0.5 # 后面0.5的调整为了画出来的结果比较好看
        self.YTranslate = rowsInMaze/2 - 0.5
        self.t = turtle.Turtle(shape='turtle')
        self.wn = turtle.Screen()  # 创建一个能在里面作图的窗口
        #self.wn.setup(width=600,height=600)
        self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,
                            -(rowsInMaze-1)/2-.5,
                            (columnsInMaze-1)/2+.5,
                            (rowsInMaze-1)/2+.5)  # 设置世界坐标系，原点在迷宫正中心。参数依次为画布左下角x轴坐标、左下角y轴坐标、右上角x轴坐标、右上角y轴坐标
        print(self.mazelist)

    def drawMaze(self):
        self.t.speed(40)   # 速度
        for y in range(self.rowsInMaze):    # 行，y坐标
            for x in range(self.columsInMaze):  # 列，x坐标
                if self.mazelist[y][x] == OBSTACLE: # 遇到墙壁，绘制box
                    self.drawCenteredBox(x+self.XTranslate,-y+self.YTranslate,'tan')
        self.t.color('black','blue')

    def drawCenteredBox(self,x,y,color):
        self.t.up() # 画笔抬起
        self.t.goto(x-0.5,y-0.5)    # 前往参数位置,这样绘制的正方形以文件的X为正中心，也就是到时候乌龟可以爬的位置
        self.t.color('black',color)
        self.t.color(color)
        self.t.fillcolor('green')
        # 设置海龟的朝向，标准模式：0 - 东，90 - 北，180 - 西，270 - 南。logo模式：0 - 北，90 - 东，180 - 南，270 - 西。
        self.t.setheading(90)
        self.t.down()   # 画笔落下
        self.t.begin_fill()
        for i in range(4):  # 转一圈
            self.t.forward(1)
            self.t.right(90)
        self.t.end_fill()

    def moveTurtle(self,x,y):
        self.t.up() # 画笔抬起
        self.t.setheading(self.t.towards(x+self.XTranslate,-y+self.YTranslate))
        self.t.goto(x+self.XTranslate,-y+self.YTranslate)   # 到目标位置

    def dropBreadcrumb(self,color): # 绘制路径原点
        self.t.dot(color)

    # 更新海归位置
    def updatePosition(self,row,col,val):   # val表明该位置是什么形式
        self.mazelist[row][col] = val   # 设置该标记状态为当前单元格的值
        self.moveTurtle(col,row)    # 移动海龟到该位置
        if val == PART_OF_PATH: # 成功的圆点的颜色
            color = 'green'
        elif val == TRIED:  # 尝试用的原点的颜色
            color = 'black'
        elif val == DEAD_END:   # 死胡同的颜色
            color = 'red'
        else:
            color = None

        if color:
            self.dropBreadcrumb(color)

    def isExit(self,row,col):
        return(row == 0 or row == self.rowsInMaze - 1 or col == 0 or col == self.columsInMaze-1)

    # 返回键对应的值
    def __getitem__(self, item):
        return self.mazelist[item]

# 探索迷宫
def searchFrom(maze,startRow,startColumn):

    # 初始位置开始尝试四个方向，直到找到出路。
    # 1.遇到障碍
    if maze[startRow][startColumn] == OBSTACLE:
        return False
    # 2. 发现探索过的路
    if maze[startRow][startColumn] == TRIED:
        return False
    # 发现出口
    if maze.isExit(startRow,startColumn):
        maze.updatePosition(startRow,startColumn,PART_OF_PATH)  # 显示出口位置
        return True

    # 都不是，更新海归位置，并绘制成正在探索颜色
    maze.updatePosition(startRow, startColumn, TRIED)  # 更新迷宫状态、设置海龟初始位置并开始尝试

    found = searchFrom(maze, startRow - 1, startColumn) or \
            searchFrom(maze, startRow + 1, startColumn) or \
            searchFrom(maze, startRow, startColumn - 1) or \
            searchFrom(maze, startRow, startColumn + 1)

    if found: # 找到出口
        maze.updatePosition(startRow,startColumn,PART_OF_PATH)  # 返回正确路径
    else:
        maze.updatePosition(startRow,startColumn,DEAD_END)
    return found

if __name__ == '__main__':
    PART_OF_PATH = 'O'  # 部分路径,可以成功的
    TRIED = '.'  # 尝试
    OBSTACLE = '+'  # 障碍
    DEAD_END = '-'  # 死胡同
    myMaze = Maze('maze.txt')  # 实例化迷宫类，maze文件是使用“+”字符作为墙壁围出空心正方形空间，并用字母“S”来表示起始位置的迷宫文本文件。
    myMaze.drawMaze()  # 在屏幕上绘制迷宫。
    print(searchFrom(myMaze, myMaze.startRow, myMaze.startCol))  # 探索迷宫